Algorithms for Molecular Biology

Many comparative analyses operate on rectangular matrices whose columns represent the same variables across observations. Phylogenomic measurements, however, are attached to tree branches. Converting locus-specific trees into a common locus-by-coordinate matrix is straightforward only when loci contain the same taxa and compatible topologies. In real datasets, missing taxa can delete reference branches or collapse adjacent branches into composite coordinates, while gene-tree discordance can cause a coordinate that survives taxon restriction to be absent from the empirical tree. Without a formal account of these changes, non-equivalent quantities may enter the same column and distinct causes of missingness may be conflated. Using standard tree-restriction operations, I first construct a provenance-retaining coordinate ledger. For each locus, every reference edge is recorded as deleted, retained individually, or incorporated into a composite coordinate whose original-edge membership is preserved. Each surviving coordinate is then assigned a recovery state by asking whether its corresponding split is displayed in the normalized empirical tree. Composite member sets generated across loci define a common column set, yielding one locus-by-coordinate state matrix. The matrix is unique because the graph reduction is unique. Retained taxa span one minimal subtree; its degree-two vertices lie on uniquely determined nonbranching paths, so suppressing them in any order yields the same reduced tree and grouping of original edges. Each edge therefore has one fate, each composite coordinate one member set, and each empirical split query one answer. Thus every locus-by-coordinate cell has one determined state under fixed labelled inputs and conventions. Fiber-split equivalence shows that projected splits faithfully encode these graph-derived edge groups, explaining why split-based implementations recover the same coordinate structure and cell states. A deterministic exhaustive validation on the six-taxon worked-example domain evaluated 14,160 primitive and composite cells across 472 normalized empirical-tree cases. Separately implemented graph- and split-side evaluators agreed in every tested cell, and two clean runs produced byte-identical canonical result files. No branch lengths are required. When valid lengths are supplied, numerical entries may be added separately by single-edge lookup or a declared selected-component-edge sum. The theorem guarantees a unique coordinate-and-state matrix under the stated inputs, not an input-independent numerical matrix or historical truth. It provides an auditable foundation for branch-wise comparative analyses under heterogeneous taxon coverage and gene-tree discordance.

The rapid growth of biological data demands scalable yet robust phylogenetic methods. Distance-based approaches are widely adopted not only in alignment-based molecular phylogenetics but also in emerging applications involving alternative distance measures. Balanced minimum evolution (BME) is an important principle in distance-based phylogenetic inference. A heuristic for BME using a taxon addition strategy was developed and provided by the FastME package, producing accurate tree topologies compared with alternative methods. However, beyond the original FastME implementation, there has been little development aimed at scaling this algorithm to the size of modern datasets. We present a significantly redesigned implementation of the BME algorithm that substantially improves computational efficiency while preserving mathematical equivalence. The key algorithmic improvement is the replacement of recursive tree traversal with flattened, incrementally growing arrays representing tree topology, traversal order and node properties. This design reduces traversal overhead, improves memory locality, and enables parallelization of the BME algorithm for the first time. Benchmarks show that our implementation delivers multiple dozen-fold speedup while consuming half the memory of FastME on datasets with tens of thousands of taxa. It can effectively analyze datasets of over 100,000 taxa, which are prohibitive with FastME. In addition, this implementation compares favorably in both efficiency and solution quality with a modern implementation of neighbor joining (NJ), an alternative BME heuristic using an agglomerative clustering strategy. Our BME algorithm has been released as part of the open-source Python library scikit-bio. It substantially broadens access to BME-based phylogenetic inference at scale.

Modern phylogenomic analyses often seek to reconstruct both vertical and reticulate evolutionary histories. While the prevalence of non-vertical evolution is increasingly appreciated, inferring networks remains conceptually challenging and computationally demanding. Following the success of quartet-based methods for handling gene tree discordance, several quartet-based network inference methods have been developed. A key insight of these methods is that level-1 networks can be constructed by first building a multifurcating tree called tree-of-blobs and then resolving each polytomy into a cycle. This two-step approach makes the problem easier both conceptually and computationally. However, these quartet-based methods often rely on noisy statistical tests of asymmetry in quartet frequencies. Moreover, they either enumerate all quartets, losing some scalability, or subsample them, losing information. We introduce BROOQS, a quartet-based method for resolving trees of blobs into a level-1 phylogenetic network. BROOQS efficiently aggregates information from all quartets around a blob without enumerating them, builds a pairwise similarity matrix, and uses robust spectral ordering algorithms to recover the cyclic ordering without relying on individual quartet symmetry tests. We prove theoretically that our spectral method is consistent under the network multi-species coalescent (NMSC) model. Across simulated and empirical datasets, BROOQS consistently improves accuracy and scalability compared to existing methods and extends to thousands of taxa.

Advances in genome sequencing have enabled phylogenomic studies involving tens or even hundreds of thousands of species. However, species tree inference has not kept pace with this growth because existing statistically consistent methods cannot scale to datasets of this scale. ASTRAL, the most widely used coalescent-based species tree estimator, remains limited by computational and memory bottlenecks that make ultra-large analyses impractical. Here we present ASTRAL-X, a complete algorithmic redesign of the ASTRAL framework that overcomes these computational limitations. By fundamentally redesigning the underlying data representations, algorithms, and computational framework, ASTRAL-X dramatically reduces running time while lowering memory requirements to nearly the size of the input-the asymptotically optimal bound-thereby enabling statistically consistent species tree inference at an unprecedented scale. ASTRAL-X preserves ASTRALs statistical guarantees and achieves accuracy comparable to state-of-the-art methods across simulated and empirical datasets while reconstructing species trees containing 200,000 and 300,000 taxa in 5 hours and 12 hours, respectively, using modest computational resources. Notably, ASTRAL-X reconstructed the evolutionary history of 9,524 angiosperm species in only 16 minutes. These results make highly accurate statistically consistent species tree inference practical at the scale demanded by emerging Tree of Life initiatives. ASTRAL-X is publicly available at https://github.com/aaniksahaa/ASTRAL-X-releases.

The exponential growth of genomic databases necessitates alignment-free methods for comparing genomes. While MinHash-based tools have revolutionized this field by efficiently estimating the Average Nucleotide Identity based on k-mer sets, they inherently discard structural genomic information. We introduce HyperSketch, a novel sketching tool that encodes the de Bruijn graph structure of a genome into a fixed-size, topology-aware vector using Hyperdimensional Computing (HDC). Unlike set-based sketches, HyperSketch encodes the transitions between adjacent k-mers into a superposition of orthogonal hypervectors. To formalize parameter selection, we also propose an analytical framework proving that graph-based sketches fundamentally require a smaller k-mer size than set-based models due to their expanded k+1 biological footprint. We benchmarked HyperSketch against Mash and HyperGen using a dataset of ~26 thousand viral reference genomes from NCBI GenBank. Under optimal parameters, we demonstrate a strong linear correlation (>99%) between the graph-based similarity computed by HyperSketch and standard MinHash distance estimates. Crucially, we show that the mathematical formulation of HyperSketch introduces a distance scaling effect that expands the dynamic range of estimates for closely related strains, providing a higher-resolution metric for sub-lineage clustering than purely compositional estimators. HyperSketch provides a computationally efficient, structure-aware alternative to traditional sketching. By natively encoding genomic syntax, it offers a new dimension of genomic comparison that excels at both high-resolution strain differentiation and deep evolutionary scaling, complementing existing nucleotide identity metrics without requiring sequence alignment.

Conventional short read DNA alignment algorithms, such as widely used BWA-MEM2, devote a substantial fraction of their execution time to seed generation. We present RosaSeed, a short read alignment algorithm, based on a configurable seeding framework, that significantly accelerates alignment while maintaining accuracy comparable to that of BWA-MEM2. RosaSeed replaces the BWA-MEM2 seeding kernel and directly supplies candidate seeds to the existing BWA-MEM2 chaining and alignment extension pipeline, producing standard SAM output suitable for downstream variant analysis. RosaSeed was evaluated on both simulated and real short read datasets, and its seeding time, fastq-to-SAM time, alignment accuracy, and memory footprint were compared against BWA-MEM2, Minimap2, Bowtie2, and the Enumerated Radix Tree (ERT) algorithm. We also compared against ERT2, a proposed simplified variant of ERT that sacrifices a small amount of alignment accuracy to significantly increase the alignment throughput. With single-threaded software execution, our recommended RosaSeed configuration achieves 13.06x and 3.85x speedups in seed processing and fastq-to-SAM time, respectively, over BWA-MEM2. Corresponding seed processing (and fastq-to-SAM) speedups are 3.96x (2.48x) over ERT, 1.2x (1.44x) over ERT2, 4.82x (3.31x) over Minimap2, and 33.24x (10.83x) over Bowtie2. RosaSeed requires only 49.61 GB of peak memory, approximately 25% less than ERT and ERT2, while maintaining alignment accuracy comparable to that of BWA-MEM2. Following the recent release of minibwa, a prefetch-optimized FM index aligner, we additionally benchmarked RosaSeed against it on an upgraded 24-core, 48-thread AMD Zen 3 workstation. Our speed-optimized miniRosaSeed configuration achieves a 2.12x fastq-to-SAM speedup over minibwa for single-threaded execution while producing 2.58% higher standard accuracy. Against Strobealign, miniRosaSeed reported a 2.18x fastq-to-SAM speedup and 3.1% higher standard accuracy. For multi-threaded execution, miniRosaSeed was both faster and more accurate than minibwa for up to 26 software threads on the Zen 3 workstation. RosaSeed provides multiple runtime-memory configurations, spanning memory-efficient and high-performance strategies, enabling users to select operating points appropriate for diverse computational environments while maintaining alignment quality comparable to that of BWA-MEM2.

DNA foundation models such as Evo2 7B adopt hybrid Hyena/attention architectures (StripedHyena2) whose single-stream autoregressive decoding is bounded by weight bandwidth at ~45 tok/s. Speculative decoding on such hybrids faces a systems problem that prior SSM work solves only partially: after a draft is verified, rolling back model state cannot be reduced to truncating a KV cache, because the inference state mixes fixed-length FIR sliding windows, infinite-memory IIR recurrences, and append-only KV caches. We present EvSpark. (i) A block-verification forward pass together with a per-position state-slicing rollback protocol handles all three state classes jointly with zero recomputation, reducing speculative overhead to 1.05-1.16x under an identity drafter and eliminating the second per-round forward pass of snapshot-and-replay schemes. (ii) A DSpark-style distilled neural drafter is ported to this hybrid architecture (gamma-parallel trunk + target hidden-state prefix + full-matrix Markov head), with an fp32-scale distillation codec required by the ~10^11 residual magnitudes of the final blocks. (iii) Under a 48-prompt (43 real + 5 synthetic) x 1024-token x 3-training-seed protocol, EvSpark delivers 3.27x on the full suite and 2.96x on real sequence at its deployment configuration (gamma=12, 150M supervised positions), holding from 1k to 262k context (1.84x-2.43x on two complete bacterial genomes at 262k) and across 32k tokens of generation depth. In exact arithmetic the scheme preserves the target distribution; empirically, greedy decoding reproduces native outputs token-for-token (zero non-tie divergences across 48 prompts x 6 checkpoints); the sampling path sits at the matched-N native noise floor for about half of 24 KL prompts per checkpoint, with the remaining deviations bounded, bf16-level, and concentrated in low-complexity repeat regions (worst-case unigram TVD 8.2%, <4% elsewhere). The budget sweet spot adds 1.06 GPU-hours of training and reaches 3.15x.

The study of evolution between species (phylogenetics) and the study of evolution within a species (population genetics) are highly related, as the same biological mechanisms are fundamental to both fields. Although both have been studied for a long time, their joint study in a unified setting has been prevented by the different time scales they consider and the different data types they employ. A similar discrepancy holds for their whole-genome specializations, comparative genomics and pangenomics. Two active areas in these fields are genome rearrangement studies and graphical pangenomics, respectively. Since the emergence of graphical pangenomics, these have existed as separate fields, despite observations that central data structures representing genomic variants in both fields are highly similar. While there exists a wealth of theoretical results for various rearrangement models in comparative genomics, the application to pangenomic data is hampered by the limitations of rearrangement problem formulations. On the practical side, pangenomes typically contain too many individual genomes for classical problems, such as the often NP-hard parsimony problems, to be solved, or for all-vs-all comparisons using rearrangement distances to be performed. On the theoretical side, some assumptions in the formulation of rearrangement problems, such as the assumption of an underlying tree, are inadequate for many pangenomes. In this work, we propose the Complete Ancestral Reconstruction for Pangenomes (CARP) problem, which overcomes these limitations while retaining intuitive relationships to both classical rearrangement problems and pangenome graphs.

Multiple sequence alignments (MSAs) are often treated as a solved problem. However, ambiguously or incorrectly aligned regions are the source of much error in phylogenetics and comparative genomics. CRAIC is a cross-platform desktop workbench that treats an alignment as a set of hypotheses to be stress-tested. CRAIC uses the posterior match probabilities of a three-state pair hidden Markov model (pair-HMM) to derive complementary views of alignment confidence. The five views are (i) a reliability overlay with live column and residue masking; (ii) a multi-aligner disagreement map, (iii) a local realignment sandbox, (iv) an interactive posterior explorer, and, where the true alignment is known, (v) a per-residue view of correctly predicted homologies. When present, MAFFT, MUSCLE, ProbCons, Clustal Omega, ClustalW and PRANK are integrated in the tool. In benchmarks the reliability score can locate misaligned columns, but while CRAIC can implement automatic filtering, it is primarily built for inspection and curation.

Z-DNA is a left-handed DNA conformation implicated in gene regulation and chromatin dynamics. Because it is usually less thermodynamically favorable than canonical B-DNA under physiological conditions, computational tools are needed to identify sequences likely to adopt the Z conformation. Legacy Z-Hunt uses a dinucleotide thermodynamic model, but searches every anti/syn assignment in a window, causing its conformation search to grow exponentially with window size. We present Z-Hunt-DP, an exact dynamic programming reformulation that preserves the original thermodynamic objective while reducing this search from O(2^d) to O(d) for a window of d dinucleotide positions. On benchmark windows, Z-Hunt-DP matched the brute-force minimum energy within numerical tolerance and achieved a 3.30x10^5 speedup at 20 dinucleotides. In an interval-localization benchmark on public human loci with experimentally mapped Z-DNA, it recovered the clipped reference interval in all 24 cases and was the most stable localizer under midpoint-core and expanded-panel analyses. Since the comparison set mixes thermodynamic, heuristic, and learned models, these cross-tool results are interpreted as localization comparisons rather than direct thermodynamic score tests. The source code and benchmark materials are available at https://github.com/Aljumaily/Z-Hunt-DP.

Dynamic programming yields exact quadratic-time (O(NM)) pairwise sequence alignments. Static banding heuristics (O(NW)) fail catastrophically on low-identity (below 30 percent), asymmetric insertions/deletions (indels), or extreme length ratios, dropping core-block Sum-of-Pairs (SP) score recovery to 20 to 50 percent. Conversely, recent protein language model (PLM) aligners evaluate all N by M cells without search grid constraints. To bridge this gap, we introduce Adaptive-Banding Needleman-Wunsch (AB-NW), leveraging PLM contextual representations to construct a confidence-adaptive dynamic programming corridor prior to fine-resolution dynamic programming while keeping downstream scoring unmodified. AB-NW downsamples residue embeddings, computes a coarse alignment, and sets per-row corridor bounds via normalized confidence metrics. Evaluated via JIT-compiled buffers, this reduces time complexity to O(NW_mean) and space to O(NW_max), where the average bandwidth is much smaller than sequence length M. Benchmarked across three PLM backbones (ESM2-8M, ESM2-35M, ProtBERT) across nine structural challenge categories, AB-NW recovers over 98.9 percent of exact unconstrained alignment scores and core-block SP accuracy across static banding failure modes (Twilight Zone, Asymmetric Indels, Extreme Aspect Ratios) while eliminating 55.3 to 78.8 percent of active dynamic programming cells. On large protein matrices (N, M greater than or equal to 3,700), AB-NW eliminates 87.6 to 91.7 percent of cells, achieving speedups of 9.79x to 13.30x (pure DP) and 1.73x to 2.94x (end-to-end), reaching up to 18.12x on unbiased controls (p less than 0.05 to p less than 10^-15), making AB-NW practical for large-scale, high-throughput sequence alignment pipelines.

RAxML-NG is a widely used tool for maximum likelihood based phylogenetic inference. In the seven years since the last RAxML-NG publication, we have continuously improved and extended the code. Here, we describe the next major release, RAxML-NG 2.0. It introduces a plethora of new features: integrated model testing, multiple fast branch support metrics, automatic parallelization tuning, phylogenetic difficulty prediction, genotype evolution models, to name but the most important ones. Furthermore, we introduce two novel search heuristics at production code level: the adaptive difficulty-aware heuristic (default) and the fast mode with early-stopping that prevents over-optimization. We perform extensive benchmarking of RAxML-NG 2.0 with respect to its accuracy and speed, and compare it to other popular maximum likelihood based phylogenetic inference tools (IQTree, VeryFastTree) as well as to preceding RAxML-NG versions. In particular, the new fast search heuristic in conjunction with machine learning based branch support prediction induces a 75x inference time reduction compared to RAxML-NG 1.2, with minor to no accuracy loss. The code is available under GNU GPL at https://codeberg.org/amkozlov/raxml-ng.

We present a lossless compression algorithm for indexing a protein database while supporting fast taxonomic classification in the method Centrifuger. The algorithm is a new scheme of the previously proposed run-block compression algorithm to reduce the size of the Ferragina-Manzini (FM) index, and it scales better with alphabet size than the original. On the RefSeq prokaryotic and viral protein sequences, Centrifuger reduces the memory footprint by over a third compared to the method Kaiju that builds on a plain FM-index, while having comparable running time. Furthermore, the compressed FM-index is lossless and can locate matches of arbitrary length, which helps Centrifuger achieve greater accuracy than Kraken2, a k-mer-based taxonomic classification method. We leverage the computational efficiency of Centrifuger to create an index of size 182 GB for classifying the reads against the full nr database that contains about 250 billion amino acid characters. Using this index, Centrifuger reveals different SARS-CoV-2 infection states and viral transcriptome profiles across human cell types from single-cell RNA-seq data.

As genomic sequencing produces increasingly massive datasets, accurate local sequence alignment via the Smith-Waterman(SW) algorithm remains computationally prohibitive due to its space and quadratic time complexity O(mn). While parallelization addresses a path forward, existing MPI-based solutions present a critical bottleneck during the traceback phase, either omitting it entirely or gathering the entire direction matrix to a single root node, which severely limits scalability. To overcome this, we propose a fully distributed Message Passing Interface (MPI) implementation featuring a token passing traceback scheme. Our approach distributes the directional matrix across all participating ranks, reducing per-rank memory footprint from O(mn) to O(mn/p), thereby enabling the alignment of sequences far beyond the capacity of sequential or centralized parallel methods. We validate our method on real human DNA sequences (BRCA1, BRCA2, Titin, chr1, chr2) and synthetic datasets up to 50kx50k. Results demonstrate that this MPI implementation aligns 98kx98k real DNA (chr1xchr2) in 58.9160 seconds across 16 MPI processes, a task where the sequential baseline fails due to out-of-memory errors. We achieve best speedups on synthetic data of 19.30x (40kx40k, 16 MPI processes) and on real DNA data is 13.39x (BRCA1xTitin, 8 MPI processes), while capping per-rank memory for the largest dataset at just 573 MB. By enabling exact, memory-scalable alignment with fully distributed traceback on standard CPU MPI clusters, this work fills a critical gap in high-performance computational genomics.

MinHash-based genome comparison is governed by two statistical constraints: a noise floor on k-mer size, controlling chance collisions between unrelated sequences, and a precision floor on sketch size, controlling uncertainty in the estimated Jaccard similarity. These constraints are best characterized for fixed-size bottom-sketch MinHash, the classical construction underlying tools such as Mash and still the standard basis for comparing genomes of similar size. Nevertheless, while, the noise floor has an established closed-form solution, sketch size is commonly selected using fixed defaults or heuristic choices independent of genome length and target precision. Moreover, recent work on scaled (FracMinHash) sketching has highlighted the difficulty of obtaining an analogous closed-form confidence interval for the Jaccard similarity. Here, we show that under the fixed-size bottom-sketch MinHash model, the shared-hash count follows a binomial model, which lets classical proportion-estimation theory be applied directly. Combining this with Fofanov's k-selection criterion and the exact identity-Jaccard relationship yields a single closed-form design rule, s* (L, {rho}* , ), that unifies the noise and precision floors into one operating envelope. The resulting design rule was validated against exact Clopper-Pearson interval inversion, idealized binomial sampling, realistic overlapping k-mer simulation and 54 bacterial genome pairs spanning species-to-order taxonomic levels. In realistic simulations, empirical coverage remained within 1-3 percentage points of the idealized reference in 14 of 15 tested cells. In real genomes, the classical identity-Jaccard relationship showed increasing positive bias with taxonomic divergence, from a median of -1.4% within species to +27% at genus and +77% at family level. We further show that s* (L) is not smooth in genome length but a discontinuous, previously unreported staircase caused by the ceiling function used for k-mer selection, with practical consequences concentrated at specific genome-size boundaries.

This study introduces a novel model that integrates the capacity of Potts models to capture structural dependencies with the computational efficiency afforded by Felsenstein's algorithm in phylogenetics. While the present work focuses on protein models, the PhyloPotts framework is equally applicable to alignments of discrete states, including RNA, DNA, and 3DI characters. Our findings indicate that, although phylogenetic estimates do not consistently exhibit reduced bias relative to standard models, the approach substantially enhances the accuracy of ancestral sequence reconstruction. The method is freely available via an open source implementation in the PhyloPotts package for BEAST 2 from https://github.com/rbouckaert/potts.

Agentic reasoning systems increasingly interact with environments whose states are only partially observed, dynamically evolving, and constrained by physical, biological, or logical structure. Existing agentic reasoning frameworks often model internal reasoning, tool use, and post-training adaptation using flat latent representations and struggle in curved manifold space environments. However, many scientific and embodied domains naturally lie on curved state spaces, including tissue geometry, developmental trajectories, protein conformations, robotic configuration spaces, and constrained physical systems. We introduce Manifold Agentic Reasoning, a geometric framework that extends agentic reasoning from Euclidean latent spaces to Riemannian manifolds. In the proposed framework, observations are encoded as manifold-valued states, memory is retrieved by geodesic similarity, candidate hypotheses are generated in tangent spaces, predicted transitions are projected by exponential maps, and decisions are admitted through verification-gated commitment or repaired by manifold self-correction. We further extend the framework to graph-agentic manifold reasoning, where node states live on manifolds and neighbor information is transported by logarithmic maps before attention-based aggregation. Manifold agent reasoning moves AI past brittle, prompt-chained templates to solve four critical production flaws: silent hallucinations and reasoning drift, brittle tool and context misuse, the black-box evaluation problem and stiff behavior profiles. To evaluate the framework, we introduce a Curved Tissue Manipulation and Recovery benchmark in which an agent must repair damaged tissue on a curved manifold. Simulated results show that the full manifold-agent substantially outperforms both a baseline reasoning agent and a full flat-agent reasoning system, achieving higher recovery success, lower geodesic shape error, lower pattern error, and fewer invalid transitions. Curvature and ablation studies indicate that the performance gain is driven by geometry-aware reasoning, verification, memory, and self-repair. These results suggest that manifold-aware agentic reasoning provides a principled foundation for reliable scientific and embodied AI systems operating in curved, constrained, or mechanistic domains.

Evo 2 is the largest openly available genomic foundation model, but its forty billion parameter configuration cannot be loaded onto a single 80 GB accelerator, placing genome-scale analysis beyond most laboratories. We present TurboQuant-Bio, an open toolkit that compresses Evo 2s weights and attention cache to four bits without calibration data, and serves both through fused kernels. Compression is near-lossless across perplexity spanning the tree of life, genomic classification, splice-site prediction, gene completion and clinically relevant variant-effect prediction. It brings Evo 2 40B onto one 80 GB GPU and Evo 2 7B to its full million-token context within a 40 GB memory budget, an eightfold gain in reachable context. We further show that the released chunked-prefill path is silently incorrect, returning plausible but uncorrelated likelihoods, and derive the block-wise continuation that repairs it: a complete 580-kilobase bacterial genome is now scored in one context in 22 minutes rather than 13.7 hours.

Nucleic acid secondary structure thermodynamic models have great utility for the analysis and design of nucleic acid structures, devices, and systems, yet their complexity and piecemeal development over decades pose challenges to further innovation. Employing different functional forms for each loop type within a structure, existing nearest neighbor (NN) models necessitate numerous loop-specific dynamic programming recursions in order to calculate physical quantities of interest. Here, we derive and implement a new class of models based on transfer matrices, yielding a single functional form for the free energy of all loop types (as the trace of a matrix product) and a single dynamic programming recursion for calculating physical quantities of interest. This new class of models has additional attractive properties: 1) incorporating a subensemble of states describing proximal interactions within each loop, 2) approximating logarithmic entropic scaling for all closed loops, 3) offering the opportunity to model correlations between the subensembles of neighboring loops by generalizing transfer matrices to tensors, and 4) providing a basis for systematically adjusting the number of model parameters to enhance accuracy as new empirical data become available for parameter regression. We use literature experimental data to regress parameters for representative new transfer matrix models, observing accuracy as good as or better than that of existing NN models, yet using dramatically fewer parameters (e.g., dozens vs hundreds or thousands). For complex ensembles containing an arbitrary number of interacting nucleic acid strands totaling N nucleotides, the new single recursion leads to exact dynamic programs for calculating diverse physical quantities (including the partition function, equilibrium base-pairing probabilities, minimum free energy and suboptimal proxy structures, Boltzmann-sampled secondary structures, and gradient of the partition function) with O(N3) time complexity. The simplicity of the new partition function dynamic program enables overflow-safe partition function calculations using renormalization to achieve scalability for large complexes (e.g., 50,000 nt) as well as formulation using a global matrix multiplication primitive that facilitates GPU acceleration, yielding speedups of an order of magnitude relative to NN partition function algorithms for large complexes. The new class of transfer matrix and tensor models provides an elegant framework for future efforts to advance the accuracy, speed, and scope of computational nucleic acid analysis and design.

For ten years, baltic (Backronymed Adaptable Lightweight Tree vIsualization Code) has been used to make annotated phylogeny figures in molecular epidemiology, including during the West African Ebola epidemic, the Zika epidemic in the Americas, and the SARS-CoV-2 pandemic, as well as other fields. At its core, baltic is a Python library used for the efficient parsing, traversal, manipulation, and visualisation of phylogenetic trees. It is a small library with few dependencies that reads tree formats common in phylodynamic analyses and gives the user leverage to interact with a lightweight tree data structure to produce publication-ready figures with matplotlib. We present baltic v1.0, its first formally released and documented version. baltic reads and writes BEAST Nexus, Newick, and Nextstrain/Auspice JSON, and can process large BEAST posterior tree files in parallel to extract user-defined posterior statistics. The same objects are used for tree manipulation and for plotting in a single script. New to this release: a set of rooting methods (midpoint rooting, rerooting on any branch, and root-to-tip regression); support for reticulate evolution, with reassortment and recombination edges; and composite figures that combine a tree with other data, such as Muller plots, skygrid plots, tanglegrams, and plots connecting trees to maps. The release includes a documentation site with an API reference, tutorials, and a matplotlib-style gallery of worked examples.